510. Inorder Successor in BST II
Medium

Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.

The successor of a node is the node with the smallest key greater than node.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for Node:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

 

Example 1:

Input: tree = [2,1,3], node = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type.

Example 2:

Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

Example 3:

Input: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 15
Output: 17

Example 4:

Input: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 13
Output: 15

Example 5:

Input: tree = [0], node = 0
Output: null

 

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -105 <= Node.val <= 105
  • All Nodes will have unique values.

 

Follow up: Could you solve it without looking up any of the node's values?

Accepted
34,682
Submissions
57,004
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.97 (30 votes)

Premium

Solution


Successor and Predecessor

Successor = "after node", i.e. the next node in the inorder traversal, or the smallest node after the current one.

Predecessor = "before node", i.e. the previous node in the inorder traversal, or the largest node before the current one.

img


Approach 1: Iteration

Intuition

There are two possible situations here :

  • Node has a right child, and hence its successor is somewhere lower in the tree. To find the successor, go to the right once and then as many times to the left as you could.

pic

  • Node has no right child, then its successor is somewhere upper in the tree. To find the successor, go up till the node that is left child of its parent. The answer is the parent. Beware that there could be no successor (= null successor) in such a situation.

pac


fic

Algorithm

  1. If the node has a right child, and hence its successor is somewhere lower in the tree. Go to the right once and then as many times to the left as you could. Return the node you end up with.

  2. Node has no right child, and hence its successor is somewhere upper in the tree. Go up till the node that is left child of its parent. The answer is the parent.

Implementation

Complexity Analysis

  • Time complexity : O(H)\mathcal{O}(H), where HH is the height of the tree. That means O(logN)\mathcal{O}(\log N) in the average case, and O(N)\mathcal{O}(N) in the worst case, where NN is the number of nodes in the tree.
  • Space complexity : O(1)\mathcal{O}(1), since no additional space is allocated during the calculation.

Report Article Issue

Comments: 12
phongtlam1223's avatar
Read More

JS recursive solution. Pretty damn proud of my code for once lmao

var inorderSuccessor = function(node) {
  if (node.right) return goDown(node.right);
  return goUp(node.parent, node.val);
};

function goDown(node) {
  if (!node || !node.left) return node;
  return goDown(node.left);
}

function goUp(node, val) {
  if (!node) return node;
  if (node.val > val) return node;
  return goUp(node.parent, val);
}

16
Show 1 reply
Reply
Share
Report
bellevue's avatar
Read More

For the second situation, just go up and find the node with greater value. No need to check if left or right:

// the successor is somewhere upper in the tree
while (x.parent != null && node.val > x.parent.val) x = x.parent;

3
Show 1 reply
Reply
Share
Report
theseungjin's avatar
Read More

Can anyone explain clearly why "Go up til the node that is the left child of its parent" logic works? I can rationalize this to myself knowing the fact but can't seem to logically explain.

2
Show 2 replies
Reply
Share
Report
Merciless's avatar
Read More

The first time I wrote almost exactly the same as the official solution:

class Solution:
    def inorderSuccessor(self, node: 'Node') -> 'Node':
        if node.right:
            node = node.right
            while node.left:
                node = node.left
            return node
        while node.parent and node.parent.val < node.val:
            node = node.parent
        return node.parent

2
Show 2 replies
Reply
Share
Report
Hieroglyphs's avatar
Read More

"Given a binary search tree and a node in it"
Where is the "node in it"? Only the tree is given. Why is the method signature not the same as 285. Inorder Successor in BST?

0
Show 4 replies
Reply
Share
Report
nikhilgoyal's avatar
Read More

Where is the use of BST properties here? The solution will be the same for BT or BST.

class Solution:
    def inorderSuccessor(self,node):
        if node.right:
            return self.leftmost(node.right)
        p=node.parent
        while p:
            if node is p.left:
                break
            node=p
            p=node.parent
        return p
        
    def leftmost(self,node):
        if not node.left:
            return node
        return self.leftmost(node.left)

0
Reply
Share
Report
smuuth's avatar
Read More

This algorithm does not use the fact that the tree is a BST. An inorder traversal is the same for a tree as a binary search tree.

0
Reply
Share
Report
hitzy's avatar
Read More

Clear code: either right exists or not. Handled both cases well:

class Solution {
    public Node inorderSuccessor(Node node) {
        if (node == null) return null;
        if (node.right != null) {
            Node cur = node;
            cur = cur.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }
        else {
            Node p = node.parent;
            Node cur = node;
            while (p != null && p.right == cur) {
                cur = p;
                p = p.parent;
            }
            return p;
        }
    }
}

0
Reply
Share
Report
skandari's avatar
Read More

Anyone confused? just think of the Inorder Traversal of the tree and visualize what will come after a node?
if it has right subtree the leftmost element of right subtree.
else the node which would have called it as its left subtree.

0
Reply
Share
Report
ZijiaqiXu's avatar
Read More

Explanation of the logic when it has no right child, for those who need:

Pre-condition:
C1. the target node has no right child (which means its successor if exists, is above it)

About the current node:
A1. all the nodes in the subtree rooted at the current node has been visited.
[since in-order traversal guarantees the order:
left-subtree --> root (current, visited) --> right-subtree(non-existent due to C1)]

There are three cases about the parenthood of the current node:
P1. has no parent: all nodes have been visited.
(the end condition of the iteration)

P2. is its parent's right child: all the nodes in the subtree rooted at its parent has been visited.
[since in-order traversal guarantees the order:
left-subtree --> root(parent) --> right-subtree(rooted at current, visited due to A1)]
(then change current node to its parent and go on)

P3. is its parent's left child: successor is its parent.
[since in-order traversal guarantees the order:
left-subtree(rooted at current, visited due to A1, where the last step is the target node) --> root(parent, succeeds from the last step, which is the target node) --> right-subtree]
(then return its parent)

The below is my code (in Java), which I think is more understandable:

    // O(H) time, O(1)space when
    // has no right child (and)
    // find the first ancestor that has node as its left descendant
    while (node.parent != null) {
        if (node == node.parent.left) return node.parent; // case 3
        else node = node.parent;// case 2
    }
    // case 1
    return null;

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.